import java.util.HashSet;
import java.util.Set;

public class FirstMissingPositive {
    // leetcode 缺失的第一个正数
    // https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked
    // 通过观察发现，可能的结果只可能是[1,n+1]之间的数
    // 如果数组中的元素都在[1,n]之间，那么最终的结果就是n+1
    // 如果数组中的出现一个不在[1,n+1]之间的元素，那么最终的结果就在[1,n]之间

    /**
     * 因为发现了结果只可能在[1,n+1]之间，所以我们先遍历一遍数组，将出现的元素存储进set中，然后从[1,n+1]看哪个
     * 元素不在set中
     * @param nums
     * @return
     */
    public int firstMissingPositive1(int[] nums) {

        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            if (!set.contains(n)) set.add(n);
        }
        int len = nums.length;
        for (int i = 1; i <= len + 1; i++) {
            if (!set.contains(i)) return i;
        }
        return -1;
    }

    /**
     * 既然我们知道结果只可能出现在[1,n+1]之间，那么我们可以使用原地哈希的方式来替换掉hashset
     * @param nums
     * @return
     */
    public int firstMissingPositive(int[] nums) {
        // 通过观察发现，可能的结果只可能是[1,n+1]之间的数
        // 如果数组中的元素都在[1,n]之间，那么最终的结果就是n+1
        // 如果数组中的出现一个不在[1,n+1]之间的元素，那么最终的结果就在[1,n]之间
        int len = nums.length;
        // 先将数组中的所有不在范围内的元素修改为不影响判断的值，不能简单的直接将元素改为正数
        for (int i = 0; i < len; i++) {
            if (nums[i] <= 0 || nums[i] > len) {
                nums[i] = len + 1;
            }
        }
        for (int i = 0; i < len; i++) {
            int tmp = Math.abs(nums[i]);
            if (tmp > 0 && tmp <= len) {
                nums[tmp-1] = -Math.abs(nums[tmp-1]);
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] >= 0) return i + 1;
        }
        return len + 1;
    }

    public static void main(String[] args) {
        FirstMissingPositive firstMissingPositive = new FirstMissingPositive();
        int[] arr = {1};
        firstMissingPositive.firstMissingPositive(arr);
        System.out.println(5455);
    }
}
